class Exon(object):
    def __init__(self,l,r,l2,r2,w):
        self.l = l;
        self.r = r;
        self.protein_l = l2;
        self.protein_r = r2;
        self.w = w;
    def __str__(self):
        return "Exon "+str(self.l)+","+str(self.r)+","+str(self.w);
    def __repr__(self):
        return str(self);

table = {}

def GetOptimalChainDirections(exons):
    pts = [0 for i in range(exons[-1].r)];
    prev = [0 for i in range(exons[-1].r)];
    last_pos = 0;
    for exon in exons:
        for i in range(last_pos+1,exon.l+1):
            if(pts[i-1] > pts[i]):
                pts[i] = pts[i-1];
                prev[i] = 0;
        last_pos = exon.l;
        if len(pts) <= exon.r:
           pts+= [0 for i in range(exon.r + 1 - len(pts))];
           pts = pts[:exon.r+1];
        if len(prev) <= exon.r:
           prev += [0 for i in range(exon.r + 1 - len(prev))];
           prev = prev[:exon.r+1];
        if pts[exon.r] < pts[exon.l] + exon.w:
            prev[exon.r] = exon;
            pts[exon.r] = pts[exon.l] + exon.w;
    return prev;

def GetExonsFromChain(exons, prev):
    result = [];
    pos = len(prev) - 1;
    while (pos >= 0 and prev[pos] == 0):
        pos-=1;
    while (pos >= 0):
        e = prev[pos];
        result.append(e);
        pos = e.l;
        while (pos >= 0 and prev[pos] == 0):
            pos-=1;

    result.reverse();
    return result;

seqDNA = "TTGTAAAATG"
seqRNA = "AAAATTGTATG";

exons = [Exon(0, 3, 4, 7, 4), Exon(4,7,0,3,4), Exon(7,9,8,10,3)];
prev = GetOptimalChainDirections(exons);
result = GetExonsFromChain(exons, prev);
for i in result:
    print i;


xpoints = [];
for e in exons:
    xpoints.append(e.l);
    xpoints.append(e.r);
ypoints = [];
for e in exons:
    ypoints.append(e.protein_l);
    ypoints.append(e.protein_r);
xpoints = xpoints.sort();
ypoints = ypoints.sort();

x = 0
for xpoint in xpoints:
    y = 0
    for ypoint in ypoints:        
        table[(x,y)] = max(table[(x-1,y)],table[
